package com.demo.java.OD101_150.OD137;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【需要广播的服务器数量】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145729816
 */
public class OdMain {
    public static int count = 0;  // 用于记录符合条件的节点数量

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入并分割成字符串数组
        String[] inputStr = sc.nextLine().split(" ");
        int n = inputStr.length;  // 获取节点数（图的大小）

        // 创建一个n * n的二维数组，用于存储图的邻接矩阵
        int[][] arr = new int[n][n];

        // 解析第1行输入，填充邻接矩阵的第一行
        for (int i = 0; i < n; i++) {
            arr[0][i] = Integer.parseInt(inputStr[i]);
        }

        // 读取剩余的邻接矩阵数据
        for (int i = 1; i < n; i++) {
            String[] s = sc.nextLine().split(" ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(s[j]);  // 将每一行的数据填充到矩阵中
            }
        }

        // 创建一个布尔数组，标记每个节点是否被访问过
        boolean[] visited = new boolean[n];

        // 遍历所有节点，若该节点未被访问过，则从该节点开始进行DFS
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(arr, visited, i);  // 从节点i开始深度优先搜索
            }
        }

        // 输出符合条件的节点数量
        System.out.println(count);
    }

    // 深度优先搜索函数
    public static void dfs(int[][] arr, boolean[] visited, int index) {
        visited[index] = true;  // 标记当前节点为已访问

        boolean flag = true;  // 标志变量，用于判断是否存在未访问的邻接节点

        // 遍历当前节点的所有邻接节点
        for (int i = index + 1; i < arr.length; i++) {
            if (arr[index][i] == 1) {  // 如果存在边，即arr[index][i] == 1
                flag = false;  // 存在未访问的邻接节点，设置flag为false
                dfs(arr, visited, i);  // 对该邻接节点进行递归DFS
            }
        }

        // 如果当前节点没有未访问的邻接节点，意味着它是一个终止节点
        if (flag) {
            count++;  // 终止节点数量+1
        }
    }
}